#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/*
插入排序是将一个记录插入到已经有序的序列中，
得到一个新的元素加一的有序序列，
实现上即将第一个元素看成一个有序的序列，
从第二个元素开始逐个插入得到一个完整的有序序列
*/

//这是伪代码
void insertSort_1(int arr[], int n)
{
    //下标0是哨兵，下标是1是直接放进去的，
    //从下标2开始排序
    int i, j;
    for (i = 2; i < n; i++)
    {
        //因为前面是有序的，所以待插入如果比有序中
        //最后一个大就不移动元素，直接插入末尾
        if (arr[i] < arr[i - 1])
        {
            arr[0] = arr[i];
            /*
            1.从有序表最后一个开始进行比较
            如果待插入元素比前面某个大的时候
            就插入到这个元素后
            */
            /*
            2.如果比较到哨兵（也就是自己也没找到）
            那么自己就是最小的，放在下标为1的位置
            */
            for (j = i - 1; arr[0] < arr[j]; j--)
            {
                //将位置向后平移一个给待排序元素插入
                arr[j + 1] = arr[j];
            }
            //此时j的位置是比哨兵小的那个元素位置
            //插入到后面
            arr[j + 1] = arr[0];
        }
    }
}

void insertSort(int arr[], int n)
{
    int i, j, tmp, elem;

    for (i = 1; i < n; i++)
    {
        elem = arr[i];
        for (j = i; j > 0; j--)
        {
            if (elem < arr[j - 1])
            {
                arr[j] = arr[j - 1];
            }
            else
            {
                break;
            }
        }
        arr[j] = elem;
    }

    return;
}

void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return;
}

void main()
{
    int arr[10] = {2, 5, 6, 4, 3, 7, 9, 8, 1, 0};
    printArray(arr, 10);
    insertSort(arr, 10);
    printArray(arr, 10);
    return;
}
